package com.dong.Arrays.arithemtic;
/*
二分法：
在升序数组nums寻找目标值target,对于特定下标i,比较nums[i]和target的大小:
    ●如果nums[i] = target, 则下标i即为要寻找的下标;
    ●如果nums[i]> target, 则target只可能在下标i的左侧;
    ●如果nums[i] < target, 则target只可能在下标i的右侧。
    于上述事实,可以在有序数组中使用二分查找寻找目标值。
二分查找的做法是，定义查找的范围[left, right,初始查找范围是整个数组。每次取查找范围的中点mid,
比较nums[mid] 和target 的大小，如果相等则mid即为要寻找的下标，如果不相等则根据nums[mid]和
target大小关系将查找范围缩小一半。于每次查找都会将查找范围缩小一半，因此二分查找的时间复杂度是O(logn),
中n是数组的长度。
二分查找的条件是查找范围不为空，即left≤right。如果target在数组中，二分查找可以保证找到
target,返回target 在数组中的下标。如果target不在数组中，则当left>right 时结束查找，返回- 1
 */
public class Demo1Correct {
    public static void main(String[] args) {
        Demo1Correct correct = new Demo1Correct();
        int[] num= {-1,0,3,5,9,12};
        int target = 0;
        int result = correct.search(num,target);
        System.out.println(result);
    }

    public int search(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            //计算中位数
            int mid = (high + low) / 2;
            int num = nums[mid];
            if (num == target) {
                return mid;
            } else if (num > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }
}
